package com.xjj.graph;

import java.util.ArrayList;
import java.util.List;

public class M0684RedundantConnection {

    List<List<Integer>> edgeList = new ArrayList<>();

    boolean hasCycle = false;

    boolean[] visit;

    public int[] findRedundantConnection(int[][] edges) {
        // 用无向图来做,初始化出边表
        for (int i = 0; i <= edges.length + 1; i++) {
            edgeList.add(new ArrayList<>());
        }
        for (int[] arr : edges) {
            edgeList.get(arr[0]).add(arr[1]);
            edgeList.get(arr[1]).add(arr[0]);
            // 每次找环都更新访问记录
            visit = new boolean[edges.length + 1];
            dfs(arr[0], -1);
            if (hasCycle) {
                return arr;
            }
        }
        return new int[0];
    }

    private void dfs(int root, int father) {
        // 先标识访问过
        visit[root] = true;
        for (int point : edgeList.get(root)) {
            // 父点不算环
            if (point == father) {
                continue;
            }
            if (visit[point]) {
                hasCycle = true;
                return;
            }
            dfs(point, root);
        }
    }
}
